// https://leetcode.cn/problems/product-of-array-except-self/

// 题干：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//      题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//      请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

// 示例：输入: nums = [1,2,3,4]
//      输出: [24,12,8,6]

// 碎语：类比前缀和思想，本题即前缀积，后缀积，因为直接算出积再用除法的话，有0的可能性

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> pre(n, 1), post(n, 1);

        // 构造前缀积，后缀积数组
        for (int i = 1 ; i < n ; i++) pre[i] = pre[i - 1] * nums[i - 1];
        for (int i = n - 2 ; i >= 0 ; i--) post[i] = post[i + 1] * nums[i + 1];

        // 遍历，重新复制原数组
        for (int i = 0 ; i < n ; i++) nums[i] = pre[i] * post[i];

        return nums;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,2,3,4};

    vector<int> index = sol.productExceptSelf(nums);
    for (const auto& num : index) cout << num << " ";
    cout << endl;

    return 0;
}